//给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。 
//
// 路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。 
//
// 
//
// 示例 1： 
//
// 
//
// 
//输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
//输出：3
//解释：和等于 8 的路径有 3 条，如图所示。
// 
//
// 示例 2： 
//
// 
//输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
//输出：3
// 
//
// 
//
// 提示: 
//
// 
// 二叉树的节点个数的范围是 [0,1000] 
// -109 <= Node.val <= 109 
// -1000 <= targetSum <= 1000 
// 
// Related Topics 树 深度优先搜索 二叉树 
// 👍 1135 👎 0

package com.cute.leetcode.editor.cn;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;

public class PathSumIii {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(10);
        TreeNode node1 = new TreeNode(5);
        TreeNode node2 = new TreeNode(-3);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(2);
        TreeNode node5 = new TreeNode(11);
        TreeNode node6 = new TreeNode(3);
        TreeNode node7 = new TreeNode(-2);
        TreeNode node8 = new TreeNode(1);

        root.left = node1;
        root.right = node2;
        node1.left = node3;
        node1.right = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
        node4.right = node8;

        TreeNode test1 = new TreeNode(0);
        TreeNode test = new TreeNode(8);
        test1.left = test;
        new PathSumIii().new Solution().pathSum(test1, 8);
    }
    public static class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
    //leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    /**
     * 参考链接：https://leetcode.cn/problems/path-sum-iii/solution/dui-qian-zhui-he-jie-fa-de-yi-dian-jie-s-dey6/
     * 使用一个队列来存放节点的信息，找一个变量sum储存队列中所有元素的和，如果当前节点与sum的和<target，入队列
     * 相等的话就统计+1，然后出队列一个，入队列一个
     * >target的话同样出一个入一个
     *
     * md 没有实现想要的结果
     * 这道题是目前我看题解最久的一道题目，而且题解还没看懂
     * 需要一个hashmap来存储前缀和（根节点到当前节点包含当前节点值的路径和）
     * key代表前缀和，value是节点的数量，即根节点到多少个节点的前缀和是一样的
     * 如果两个节点的前缀和的差为target，则说明从初始节点的下一个节点到终点的距离就是target
     * 当从一个根节点左右递归结束后，需要恢复map中的状态，否则再另一个根节点进行递归时可能会发生混乱
     *
     * 有两点不是非常的理解
     *  1.初始时hashmap.put(0,1)，为什么一开始先这样附一个值？前缀和为0的节点个数为1
     *  2.遍历完所有子节点之后的恢复操作
     */
    int target;
    HashMap<Integer,Integer> prefixMap;
    Queue<Integer> queue = new LinkedList<>();
    public int pathSum(TreeNode root, int targetSum) {
        this.target = targetSum; // 目标值
        prefixMap = new HashMap<>(); // 储存前缀和
        /**
         * 这是因为任何节点本身也可以形成一个路径（长度为1的路径）。
         * 如果某个节点的值就为target，那么它本身就是一个解。
         * 前缀和为0正好可以与它形成这个解。对任何节点而言，本身就是解最多只能有一个，所以一开始put(0, 1)。
         * 相当于给所有节点一个可单独形成合法路径的机会。
         * 确实是这样，可以拿单独节点试一下，或者0-8 目标为8来试一下，就是为了让单独节点=目标值时多加一次
         */
        prefixMap.put(0, 1);
        return recur(root, 0);
    }
    public int recur(TreeNode node, int curSum){
        if (node == null) {
            return 0;
        }
        int res = 0;
        curSum += node.val; //得到当前的前缀数
        // 当前节点距离根节点间的距离就是前缀数的差值
        res += prefixMap.getOrDefault(curSum-target, 0); //看看是否存在满足当前前缀数和目标差值的前缀数
        prefixMap.put(curSum, prefixMap.getOrDefault(curSum, 0)+1); //保存当前前缀数

        int left = recur(node.left, curSum); //递归
        int right = recur(node.right, curSum);
        res += left + right; // 这里将当前与子树中所有的可能的情况相加
        // 因为根节点只能对子节点造成影响，所以这里必须回溯
        prefixMap.put(curSum, prefixMap.get(curSum)-1); // 将当前前缀数的节点数减一，因为会跨过根节点，影响到其他子树的查找
        // 返回值是当前节点满足条件的数量+左右子节点满足条件的节点数量
        return res;
    }

}
//leetcode submit region end(Prohibit modification and deletion)

}